import random

def generate_array(m, n):
    total_elements = m * n
    numbers = list(range(1, total_elements + 1))
    random.shuffle(numbers)
    array = [numbers[i:i+n] for i in range(0, total_elements, n)]
    return array


def print_matrix(matrix):
    for row in matrix:
        for c in row:
            print(c, end='\t')
        print('')
    print('')


def max_path_sum(matrix):
    if not matrix:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])
    max_sum = float('-inf')  # 初始化最大和为负无穷
    current_list = []

    def dfs(i, j, path_sum):
        nonlocal max_sum
        max_sum = max(max_sum, path_sum)  # 更新最大和
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右四个方向
        for dx, dy in directions:
            x, y = i + dx, j + dy
            if 0 <= x < rows and 0 <= y < cols and matrix[x][y] > matrix[i][j]:
                dfs(x, y, path_sum + matrix[x][y])  # 继续深度优先搜索

    for i in range(rows):
        for j in range(cols):
            dfs(i, j, matrix[i][j])  # 从每个位置开始进行深度优先搜索

    return max_sum


def max_path_sum2(matrix):
    if not matrix:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])
    max_sum = float('-inf')  # 初始化最大和为负无穷
    current_list = []

    def dfs2(i, j, path: list, path_sum):
        nonlocal max_sum
        if path_sum > max_sum:
            max_sum = path_sum
            print(path)

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右四个方向
        for dx, dy in directions:
            x, y = i + dx, j + dy
            if 0 <= x < rows and 0 <= y < cols and matrix[x][y] > matrix[i][j]:
                path.append((x,y))
                dfs2(x, y, path, path_sum + matrix[x][y])  # 继续深度优先搜索
                path.pop()

    for i in range(rows):
        for j in range(cols):
            path_list = [(i,j)]
            dfs2(i, j, path_list, matrix[i][j])  # 从每个位置开始进行深度优先搜索

    return max_sum

TEST = False
if TEST:
    # # 示例用法
    # matrix = [
    #     [-1, 2,  3],
    #     [4,  5,  6],
    #     [7,  8,  9]]
    # print(max_path_sum2(matrix))  # 输出: 28

    # matrix = [
    #     [6,  2,  5,  12], 
    #     [9,  7,  -3,  4 ], 
    #     [10, 15, 16, 1 ], 
    #     [8,  11, 13, 14]]
    # print(max_path_sum2(matrix))
    for _ in range(20):
        matrix = generate_array(20, 20)
        print_matrix(matrix)
        print(max_path_sum2(matrix))
        print(max_path_sum(matrix))
else:
    from Solution import Solution
    s = Solution()
    for _ in range(20):
        matrix = generate_array(
            random.randint(3, 20),
            random.randint(3, 20)
        )
        r1 = max_path_sum(matrix)
        r2 = s.answer(matrix)
        if r1 != r2:
            print("Test Failed\nInput:", matrix, "\nExpected:", r1, "\nGot:", r2)
            exit(1)
    exit(0)